//给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。 
//
// 示例 1: 
//
// 输入: "(()"
//输出: 2
//解释: 最长有效括号子串为 "()"
// 
//
// 示例 2: 
//
// 输入: ")()())"
//输出: 4
//解释: 最长有效括号子串为 "()()"
// 
// Related Topics 字符串 动态规划 
// 👍 915 👎 0

package leetcode.editor.cn;

import java.util.Stack;

//Java：最长有效括号
public class P32LongestValidParentheses {

    /**
     *
     * 思路: 网上找的答案 =_= ,原本是想用栈的方法，左入栈，右出栈，看看匹配了几对，结果*2，然后 发现有 ()(() 这种情况，我输出是4，就错了
     *
     * 网上的思路，是先入栈一个-1，然后入栈左括号的下标做起始序号，匹配完出错的下标 - 站内的那一个值就是长度。因为一对正确的，出站入栈肯定最后站内只剩下起始下标的。
     *
     * 执行用时： 3 ms , 在所有 Java 提交中击败了 51.98% 的用户 内存消耗： 39.6 MB , 在所有 Java 提交中击败了 72.27% 的用户
     *
     */
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int longestValidParentheses(String s) {
            Stack<Integer> stack = new Stack<>();
            int max = 0;
            stack.push(-1);

            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == '(') {
                    stack.push(i);
                } else {
                    stack.pop();
                    if (stack.isEmpty()) {
//                        错误的右括号
                        stack.push(i);
                    } else {
                        // 正确的右括号
                        int len = i - stack.peek();
                        if (len > max) {
                            max = len;
                        }
                    }
                }
            }
            return max;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        Solution solution = new P32LongestValidParentheses().new Solution();
        System.out.println(solution.longestValidParentheses("()) ()((()())"));
        // TO TEST
    }

}